package com.yaoli.ajob;

import java.util.PriorityQueue;
import java.util.*;

/**
 * Created by will on 2017/5/3.
 */
public class _239_SlidingWindowMaximum {
    public static void main(String[] args) {
        _239_SlidingWindowMaximum priorityQueueTest = new _239_SlidingWindowMaximum();
        int nums [] = {2,3,4,2,6,2,5,1};
        priorityQueueTest.maxInWindows(nums,3);

        Integer [] set = new Integer[4];
        System.out.println(set[3]);
    }

    public int[] maxInWindows(int [] nums, int k){


        Comparator<Integer> comp = new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2){
                return o2-o1;
            }
        };

        //这里 初始容量必须大于 0
        PriorityQueue<Integer> priqueue = new PriorityQueue<Integer>(comp);

        Queue<Integer> queue = new LinkedList<Integer>();

        ArrayList<Integer> res = new ArrayList<Integer>();

        int temp [] = new int[0];

        if(k == 0){
            return temp;
        }

        if(k > nums.length){
            return temp;
        }

        for(int i = 0 ; i < k; i ++){
            queue.add(nums[i]);
            priqueue.add(nums[i]);
        }

        priqueue.remove();
        for(int i = k; i < nums.length ; i++){
            //int temp = priqueue.peek();
            res.add(priqueue.peek());
            queue.add(nums[i]);
            priqueue.remove(queue.poll());
            priqueue.add(nums[i]);
        }
        //注意 最后一定 还要再获取一遍
        res.add(priqueue.peek());

        int result [] = new int[res.size()];

        for(int i = 0 ; i < res.size() ; i++){
            result[i] = res.get(i);
        }

        return result;
    }
}
